// 319.灯泡开关
package Leetcode;

public class Solution319 {
    public int bulbSwitch(int n) {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            int x = 1 << n;
            out(x);
            while ((x >> i) != 0)
                out(x);
            result ^= x;
        }
        System.out.println(result);
        int count = 0;
        while (result != 0) {
            if ((result & 1) == 1)
                count++;
            result >>= 1;
        }

        return count;
    }

    private String out(int x) {
        StringBuilder sb = new StringBuilder();
        while (x != 0) {
            sb.append(x & 1);
            x >>= 1;
        }
        return sb.toString();
    }
}
